package 双指针;

import java.util.Arrays;

public class findUnsortedSubarray581 {
    /**
     * 给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
     * 采用的暴力的方法的来实现
     *
     * @param nums
     * @return
     */
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        int[] newNums = Arrays.copyOf(nums, len);
        Arrays.sort(newNums);
        int left = 0;
        int right = len - 1;
        // 开始是向左开始查询
        for (int i = 0; i < len; i++, left++) {
            if (nums[i] != newNums[left]) {
                break;
            }
        }
        // 开始是向右开始查询
        for (int j = len - 1; j >= 0; j--, right--) {
            if (nums[j] != newNums[right]) {
                break;
            }
        }
        // 如果原理就是的有序的 那就的判断就行了 否者就需要用右边-左边的结果。
        if (left == len && right == -1) {
            return 0;
        } else {
            return right - left + 1;
        }
    }

    /**
     * 采用的优化的算法
     *
     * @param nums
     * @return
     */
    public int findUnsortedSubarrayV2(int[] nums) {
        int len = nums.length;
        int l = 0, r = len - 1;
        int max = nums[0];
        int min = nums[len - 1];
        //找到最大值
        for (int i = 0; i < len; i++) {
            if (max <= nums[i]) {
                max = nums[i];
            } else {
                l = i;
            }
        }
        //找到最小值
        for (int i = len - 1; i >= 0; i--) {
            if (nums[i] <= min) {
                min = nums[i];
            } else {
                r = i;
            }
        }
        // 如果有序
        if (l == 0 && r == len - 1) {
            return 0;
        }else {
            return l-r+1;
        }
    }
}
